\chapter{Introdução}
  
  	A aviação é o principal meio de transporte capaz atravessar grandes distâncias, a sua utilização é fundamental para o crescimento das empresas e também para o desenvolvimento do turismo mundial. O transporte aéreo é um serviço que oferece beneficios de ordem social e de ordem econômica. Por ser utilizado no turismo e no comércio, ele contribui para o crescimento da economia mundial e é essencial para o rápido transporte de pessoas e de mercadorias ao redor do mundo. Finalmente, o transporte aéreo melhora a qualidade de vida das pessoas proporcionando lazer e experiências com outras culturas.
  	
  	O uso da aviação comercial tem crescido significativamente nas últimas décadas. Esse rápido crescimento pode ser atribuído a um grande número de fatores. Primeiro, o aumento da renda e da qualidade de vida em muitas partes do mundo que tem incentivado as pessoas a viajar para outras áreas e explorar novas oportunidades. Segundo, a demanda tem aumentado junto com a confiança na aviação como um meio seguro de viajar. Terceiro, o aumento da eficiência nas operações tem acirrado a competitividade e reduzido as taxas e os custos das passagens. Finalmente a globalização tem forçado a viagem de pessoas para fazer negócios em outros país e também para aperfeiçoar as relações políticas e sociais. Espera-se que os impactos desses fatores continuem a acontecer porém com intensidades diferentes.
  	
  	O aumento do número de companhias aéreas tem aumentado a necessidade de obtenção de melhores benefícios,como a redução dos custos e aumento das receitas. Porém os problemas presentes na indústria aeronáutica são complexos envolvendo múltiplas decisões conflitantes que precisam ser otimizadas de uma só vez. Diversas técnicas são desenvolvidas e usadas para tentar melhorar o planejamento e a operação das empresas aéreas. Muitas dessas técnicas estão disponíveis na literatura científica, nos campos da pesquisa operacional e da matemática e normalmente são modelados para funcionar em sistemas computadorizados de alta capacidade com a finalidade de automatizar, ou pelo menos auxiliar a tomada de decisões. Essas técnicas se tornam mais necessárias a medida que a empresa aérea cresce e a tomada de decisão, baseada nos julgamentos individuais e nas experiências, se tornam mais difíceis \cite{ahmed2009}.
  	
	Os principais problemas relacionados dizem respeito ao planejamento, envolvendo a criação de linhas de trabalho tanto para as aeronaves quanto para a tripulação. O objetivo costuma ser a minimização dos custos operacionais ou a maximização dos rendimentos. Custos operacionais consiste, por exemplo, nos custos envolvidos com combustíveis, óleo, taxas de aterrissagem. Também pode ser levado em consideração a perda de rendimentos com a utilização de aeronaves com menos assentos do que a demanda de passageiros, porém fatores como bem estar dos passageiros também podem ser levados em consideração.  	
	
	A modelagem de mercado é o problema que inicia essa cadeia e é a parte responsável pelo planejamento dos voos de cada região baseado na demanda de passageiros.
	
	Os problemas de planejamento que envolvem as aeronaves mais estudados na literatura são a Atribuição de Frota (\textit{Fleet Assigment}) e a Construção de Trilhos de Aeronaves (\textit{Aircraft Rotation}). E os que envolvem a tripulação são conhecidos como Construção dos Dias de Trabalhos da Tripulação(\textit{Crew Pairing}) e a Escala de Tripulantes (\textit{Crew Scheduling}).
	  	    
    O problema de Atribuição de Frota determina o tipo de equipamento a ser utilizado em cada voo \cite{pimentel2005}. O problema de construção de trilhos de aeronaves (PCTA) é o foco desse trabalho e será descrito mais adiante. O problema de construção dos dias de trabalho da tripulação visa obter o melhor conjunto de pairings\footnote{Pairing é o conjunto de voos que pode ser guiados por uma tripulação sem que seja violadas quaisquer regras da legislação vigente e que ao final do último voo o tripulante esteja de volta a sua cidade base.} tal que cada voo seja coberto por pelo menos um pairing. Gastos com alojamentos, alimentação, transporte em terra e deadheads\footnote{Deadhead é o voo que o tripulante viaja sem trabalhara com a finalidade de transporte para outra localidade normalmente para sua base ou para suprir uma nova demanda.} devem ser levados em consideração. O problema de construção das escalas dos tripulantes tem o objetivo de atribuir os pairings a tripulação disponível na companhia aérea, acrescentando as atividades de solo tais como call\footnote{Call é o tempo que a tripulação tem para se apresentar a companhia aérea antes de iniciar de fato seu turno de trabalho.}, Stand-by duties\footnote{Stand-by duties são turnos em que o tripulante fica a disposição da companhia aérea afim de suprir possíveis eventualidades.} e dias de descanso. O objetivo dessa etapa é fazer uma distribuição da forma mais justa possível, tentando balancear a quantidade de trabalho (horas a serem voadas) entre os tripulantes, e também tentar cumprir todas as solicitações da tripulação em relação a preferência dos dias de descanso e das tarefas a serem realizadas, sem violar nenhuma restrição da legislação trabalhista em vigor.
    
Após as designação da frota de aeronaves ao conjunto de voos existentes segue-se o problema de construção de trilhos de aeronaves (PCTA) \abbrev{PCTA}{Problema de Construção de Trilhos de Aeronaves} que também é conhecido na literatura como Aircraft Rotation Problem (ARP) \abbrev{ARP}{Aircraft Rotation Problem}. O PCTA é um dos principais problemas presentes na industria da aviação. No PCTA o objetivo é a construção, para cada uma das frotas da companhia (e para os voos a elas alocados), de sequências encadeadas de voos que possam ser operados por uma única aeronave \citep{abiliolivro}. Cada uma dessas sequências recebe o nome de trilho e o conjunto desses trilhos é chamado de malha aérea.

Para resolver o PCTA, devemos estar cientes de algumas restrições que envolvem tempo e espaço. Por exemplo, um voo não pode iniciar antes da chegada do voo que lhe antecede, nem de um local diferente da cidade de destino deste voo antecessor, esses exemplos são denominados respectivamente de restrições temporais e geográficas do problema. Há também a restrição de que um voo deve permanecer em solo, entre conexões, por um período de tempo que seja suficiente para fazer a troca de passageiros e abastecimento da aeronave e quando for o caso para a mudança da tripulação, esse tempo varia de acordo com o aeroporto e com o tipo de aeronave. 

Existe também a restrição de consistência que está presente em instâncias que possuem frequência. Nessas instâncias um voo pode aparecer em diversos dias. Dessa forma deve-se garantir que o horário de partida desse voo seja o mesmo em todos os dias que ele ocorrer, ou seja, caso alguma modificação seja feita no horário de partida sugerido desse voo, em um dos dias, então todos os outros dias da frequência também devem ser modificados.

Outro aspecto importante diz respeito às restrições de manutenção. Sabe-se que um avião deve ter checagens periódicas. Oportunidades de realizar essas tarefas ocorrem apenas em algumas conexões potencialmente disponíveis. Como consequência, uma sequência de voos deve ser construída de forma que essas restrições não sejam violadas. A fim de incorporar essas restrições facilmente ao nosso framework, assumimos que as rotações são designadas a tipos não específicos de aeronave. Dessa forma, se uma aeronave tem necessidade de manutenção, um voo especial é criado com origem e destino na base de manutenção escolhida e com a sua duração exatamente igual ao tempo de manutenção  \cite{pontes2002}.

	Vale ressaltar ainda que na resolução do PCTA deve-se levar em consideração as particularidades especificas de cada companhia aérea como o número de aviões disponíveis na frota, o atraso máximo permitido nos voos, a quantidade máxima de voos que podem sofrer atraso, o número máximo de voos que podem ser cancelados, o número máximo de voos de reposicionamento que podem ser criados entre outros.
	
	De uma maneira geral, o principal objetivo do PCTA é a minimização do número de trilhos seguido da minimização do custo total dos trilhos gerados. Esse custo pode envolver diversos componentes, sendo o tempo médio diário de utilização das aeronaves um dos mais importantes \citep{abiliolivro}.
  
%Aqui já nao descreve mais o problema.  
  
	 Nos dias de hoje, com o avanço da tecnologia e o aumento da competitividade desenvolver soluções com melhor qualidade acaba se tornando um fator decisivo para a permanência no mercado, tornando-se então necessário a obtenção de soluções de forma mais rápida, mais barata e utilizando menos recursos. Por causa da dificuldade que é inerente a essa classe de problemas a qualidade das soluções obtidas manualmente são muito aquém da melhor solução possível. Outra  característica que reforça a necessidade da obtenção de melhores soluções é o aumento do tamanho e da complexidade das instâncias trabalhadas. A partir desse cenário pode-se perceber a necessidade de utilização de técnicas de otimização. Na literatura tem-se observado um crescimento no número de trabalhos que se utilizam de metaheurísticas como método de resolução de problemas complexos de otimização combinatória.	  
  
	As metaheurísticas podem ser definidas como um conjunto de procedimentos de caráter geral, com capacidade de guiar o procedimento de busca, tornando-o capaz de escapar de ótimos locais. Elas têm como objetivo, encontrar uma solução tão próxima quanto possível da solução ótima do problema com baixo esforço computacional. Em geral, as metaheurísticas são bastante utilizadas na resolução de problemas de otimização. Esses problemas, também conhecidos como problemas NP-difíceis\abbrev{NP}{Non-Polinomial}, podem ser definidos como um conjunto de problemas para os quais ainda não existe um algoritmo que os resolvam de forma exata e em tempo polinomial \citep{maritan2009}. Para esses tipos de problemas o uso de métodos exatos é bastante restrito, uma vez que o esforço computacional para encontrar uma solução exata em instâncias reais é consideravelmente alto. Na prática, no entanto, é suficiente encontrar uma solução melhor que a utilizada no ambiente operacional. 


%Essa parte deveria ir para a revisão da literatura.
	A literatura pesquisada mostra uma grande quantidade de tentativas de resolver o problema utilizando modelagens matemáticas, que apesar de garantir a solução ótima não se mostra viável para resolver grandes instâncias. Alguns trabalhos mostram a similaridade desse problema com o problema do caixeiro viajante assimétrico \cite{clarke97}. E outros resolvem uma parte do problema utilizando metaheurísticas \cite{arguelo1007}.
%#############################################
%{\large >>>> Descrever em que tem se baseado a solução desse problema na literatura <<<<}
%#############################################

	Nesse trabalho é proposto o desenvolvimento de um método híbrido baseados em metaheurísticas e em programação linear inteira para resolução do PCTA. O método proposto procura combinar a eficiência computacional das metaheurísticas com a rápida convergência dos métodos exatos. Além disso ficou constatado pelo levantamento da literatura acerca do PCTA que se tem uma falta de instâncias sobre o problema que permitam uma melhor comparação dos resultados obtidos, logo também propomos a criação de um conjunto de instância baseado em instâncias reais modificando seus tamanhos e complexidades. 

%#############################################
%{\large	>>>> Fazer uma breve descrição de programação linear, maiores detalhes serão dados na fundamentação teórica. <<<<	}
%#############################################

\section {Objetivos do trabalho}

Tendo em vista os aspectos apresentados, o objetivo principal dessa proposta de trabalho consiste no desenvolvimento de um método híbrido baseado nas metaheurísticas GRASP e ILS e em programação linear inteira para a resolução do problema construção de trilhos de aeronaves (PCTA). O método proposto tem a finalidade de explorar a eficiência computacional, e irá ser combinada com etapas de refinamentos composta por métodos exatos para acelerar a convergência e adicionalmente fugir de mínimos locais.

Além disso irá ser proposto um conjunto de instâncias baseados em uma instância reais variando em complexidade e tamanho, essas instâncias irão permitir uma melhor comparação desse trabalho com outros.

\section {Organização da proposta }

O trabalho está estruturada da seguinte forma:

\begin{itemize}

\item Capítulo 1: Apresenta a motivação e as vantagens de resolver o PCTA utilizando metaheurísticas e programação linear e enfatiza a importância desse problema na indústria aeronáutica. Ao final os objetivos do trabalho são descritos.

\item Capítulo 2: Apresenta a fundamentação sobre a otimização, metaheurísticas e programação linear. Na seção referente à otimização além da descrição serão discutidos heurísticas construtivas. A seção referente às metaheurísticas irá iniciar com uma descrição seguida do detalhamento das metaheurísticas utilizadas no trabalho, como o GRASP e o ILS. Ao final da fundamentação teórica será feita uma revisão dos principais trabalhos relacionados ao presente trabalho que estão presentes na literatura.

\item Capítulo 3: Mostra como foi obtida a malha da companhia de transporte aéreo TAM e qual a estratégia será utilizada para geração das novas instâncias.

\item Capítulo 4: Descreve o problema, explicando os conceitos que serão utilizados no trabalho.

\item Capítulo 5: Introduz o modelo matemático que foi desenvolvido.

\item Capítulo 6: Descreve o método proposto nesse trabalho, mostrando como foi feita a integração das metaheurísticas e da programação linear inteira e também descreve os parâmetros e as restrições que foram utilizadas.

\item Capítulo 7: Apresenta alguns resultados preliminares que já foram obtidos com o solver, dá diretrizes de como utilizar o método proposto e indica o que se espera ter para finalizar o trabalho.
%\item Capítulo 8: Dá uma conclusão, indicando o que tem que ser melhorado e o que se espera ter para a finalização do trabalho.

\item No final é apresentado a bibliográfia estudada, o cronograma de trabalho proposto durante os 24 meses de mestrado e os anexos que contém um maior detalhamento das instâncias e dos resultados obtidos.

\end{itemize}